#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/validate-stack-sequences/

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

        // stack<int> s;
        // s.push(pushed[0]);
        // int i = 1, n = pushed.size(), j = 0;
        // while(j < n)
        // {
        //     if(!s.empty() && s.top() == popped[j]) 
        //     {
        //         s.pop();
        //         j++;
        //     }
        //     else
        //     {
        //         if(i < n) s.push(pushed[i++]);
        //         else return false;
        //     }
        // }

        // return true;

        stack<int> s;
        int i = 0;
        for (auto a : pushed)
        {
            s.push(a);
            while (!s.empty() && s.top() == popped[i])
            {
                s.pop();
                i++;
            }
        }
        return s.empty();
    }
};